package ai.zixing.mashibing.basic_class.class12;

import java.time.chrono.MinguoDate;
import java.util.HashMap;

/**
 * 给定数组arr，arr中所有的值都为正数且不重复
 * 每个值代表一种面值的货币，每种面值的货币可以使用任意张
 * 再给定一个整数 aim，代表要找的钱数
 * 求组成 aim 的方法数
 */
public class Code09_CoinsWay {

    public static int ways1(int[] arr, int aim) {
        if (arr == null | arr.length == 0 || aim < 0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }

    // 自由选择使用 arr[index...] 面值，每一种可以使用任务张，组成 rest 这么多钱，返回方法数
    public static int process1(int[] arr, int index, int rest) {
        // for 循环中可以避免出现 rest < 0 的情况， 此 base case 可以省略
//        if (rest < 0) {
//            return 0;
//        }
        // 没有货币可以选择了
        if (index == arr.length) {
            // 刚好 rest == 0时，只有这一种
            return rest == 0 ? 1 : 0;
        }
        // 当前有货币，枚举张数， arr[index]
        int ways = 0;
        for (int count = 0; count * arr[index] <= rest; count++) {
            ways += process1(arr, index + 1, rest - (count * arr[index]));
        }
        return ways;
    }

    public static int ways2(int[] arr, int aim) {
        if (arr == null | arr.length == 0 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][aim + 1];
        // 一开始没有计算，初始化为 -1
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(arr, 0, aim, dp);
    }

    // dp[index][rest] = -1 是没有计算过的，反之是计算过的
    public static int process2(int[] arr, int index, int rest, int[][] dp) {
        if (dp[index][rest] != -1) {
            return dp[index][rest];
        }
        if (index == arr.length) {
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        int ways = 0;
        for (int count = 0; count * arr[index] <= rest; count++) {
            ways += process2(arr, index + 1, rest - (count * arr[index]), dp);
        }
        dp[index][rest] = ways;
        return ways;
    }

    public static int ways3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        // for (int count = 0; count * arr[index] <= rest; count++) {
        //             根据下一行得出该行的值
        //            ways += process1(arr, index + 1, rest - (count * arr[index]));
        //        }
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int count = 0; count * arr[index] <= rest; count++) {
                    ways += dp[index + 1][rest - (count * arr[index])];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    public static int ways4(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {5, 10, 50, 100};
        int sum = 1000;
        System.out.println(ways1(arr, sum));
        System.out.println(ways2(arr, sum));
        System.out.println(ways3(arr, sum));
        System.out.println(ways4(arr, sum));
    }
}
